package com.dyz.leetcode._12_linkedList;

import com.dyz.leetcode.ListNode;

public class _19_removeNthFromEnd {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if (head == null) {return null;}
        ListNode dummyNode = new ListNode(-1);
        dummyNode.next = head;
        // 1. 计算链表长度
        int length = 0;
        ListNode curr = dummyNode;
        while (curr != null) {
            length++;
            curr = curr.next;
        }
        // 2. 找到倒数第 n 个节点的前一个节点
        ListNode prev = dummyNode;
        for (int i = 1; i < length - n; i++) {
            prev = prev.next;
        }

        // 3. 删除倒数第 n 个节点
        ListNode delNode = prev.next;
        prev.next = delNode.next;
        delNode.next = null;
        return dummyNode.next;
    }

    // 快慢指针
    public ListNode removeNthFromEnd1(ListNode head, int n) {
        if (head == null) {return null;}
        ListNode dummyNode = new ListNode(-1);
        dummyNode.next = head;
        ListNode slow = dummyNode;
        ListNode fast = dummyNode;
        //fast先走n+1步
        while(n-- >=0){
            fast = fast.next;
        }

        while (fast!=null){
            fast = fast.next;
            slow = slow.next;
        }

        ListNode delNode = slow.next;
        slow.next = delNode.next;
        delNode.next = null;

        return dummyNode.next;
    }
}
